The primary problem with the old search engine was that it took over 40 seconds to return results and slowed down the rest of the site when people used it. The new one returns results in under a second.
I think that the original 2 complaints were about the thumbnails. While previously the search took 40 seconds, now the search only takes 0.2 seconds but waiting for the thumbs over a slow, or saturated link may make it less than perfect.
Perhaps a wait do do a non-graphical search? text-only results?